For this project, I built a compiler from scratch in C# for a language of my design.
The language grows and adds features based on what the user is attempting to do, explaining new features as they come in an attempt to teach programming as it is performed.
The components of a compiler are laid out in “Modern Compiler Implementation in Java” by Appel, my system uses a modification of this standard architecture, both to support the growing language functionality and to remove functionality that the .NET runtime makes redundant (e.g. the CIL handling functions first class and not requiring you to implement them)
My lexer is a simple state machine that is documented in the DFA diagram below, this step simply takes user input and collects characters into more meaningful tokens.
I used recursive descent to implement the parser described in the BNF diagram below, this step takes the tokens from the Lexer and computes a tree to represent their structural meaning.
For these steps, we can simply recursively traverse the AST, and either check conditions on our children, or define recursive rules that convert Nodes into executable code
To test my language, I created a simple custom file format to enumerate test cases and check their outputs, be that Errors or text.
The same format is used here for non-error testing
Given the following assembly instructions, make a simple OS with shell and a high-level language:
(i and * are to indicate optional immediate/indirect addressing respectively, commands work with direct addressing by default)
lda(i/*): Load value in accumulator
sta(*): Store accumulator in memory
add(i): Add to acc
sub(i): Sub from acc
mul(i): Multiply with and store in acc
and(i): bitwise And with acc
or(i): bitwise Or
xor(i): bitwise Xor
not: bitwise Not
rshift(i): right shift acc by value
lshift(i): left shift acc by value
jmp(i): jump execution to address
jz(i): jump if previous calculation resulted in 0
jnz(i): jump if non-zero
jn(i): jump if negative
stop: End execution
Assume Lazy Terminal Interface:
printa: print acc as signed int (Optional but good for debug, Implement in hardware with BCD to so many digits)
printachar: print acc as character
getchar: get single character from keyboard
I began by implementing a macro system that would allow me to write assembly code in a way that more closely resembles C-Style programming (in practise to build this computer “from scratch” you would need to expand these macros on paper by hand)
When this project is completely finished this process will be well documented in code to attempt to make reading the source as obstacle free as possible.
I decided to build a forth as the next level of abstraction for this machine due to its relatively simple implementation and excellent meta-programming abilities, as well as its REPL environment which makes the language double as a SHELL due to low level access, the snapshots above are taken from a file containing assembly with macros that implements a basic forth kernel, heavily guided by the excellent jonesforth.
The resulting kernel is a very barebones forth, but because forth is forth, we can extend it, within forth!!!
We begin by defining soft built-in types for our system e.g.
We then create a section in memory to act as a separate local variable stack
And can now define a syntax for functions
We then define structs
Which is simply a syntax that generates many functions via meta-programming to handle areas of data as a “firstStructType”
These structs also contain an initial element that indicates their type, giving us dynamic typing!!
We can make pseudo-OOP types using structures and functions/methods that are intended to act upon those structs
Showcasing this in action:
Next up will be dynamic memory and eventually implementing an actual parser to enforce Syntax (to catch human error), Come back later to see more.
How do we get from nothing to programming? if you’ve looked at the previous section you’ve seen how I have personally started from assembly/machine code, but how do you even get that running? How do you program with no programming language?
Well, it turns out, there is a “programming language” that can be implemented quite simply with electrical circuits… Logic Gates!!!
My first attempt at simulating this process happened many years ago
I tried with a drag and drop simulator, it got unruly.
More recently I have reattempted using Verilog, a language that can be used as a markup for systems of Logic Gates
A D Flip Flop is one way to implement storage of a single bit using logic gates
This Verilog code uses
assign: To link wires to each other or:
when used with & in the expression, to implement an And gate
When used with | you get an or gate
When used with ? and : you get a tristate buffer or a multiplexer (these can themselves be implemented using combinatorial logic)
nor(): To implement a nor gate
A diagram of the above code would be
For simplicity, the initial design of this system will use an 8-bit word length, so we will simply connect 8 of these DFlipFlops to make 1 register
To implement ram, we can think of an address in binary e.g. 011001 as a list of switches
To build the RAM recursively, we start with a single register
And then we take 2 of those, and use the lowest bit to decide which to go to (if its 0 go left, if 1 go right)
Now we can take 2 of those, and use the next lowest bit to choose between those
We now have 4 registers indexed by a 2-bit address
If we repeat this recursive process we can end up with a RAM with 2^n number of registers/addresses
We now have memory and registers to operate on, but how do we define the actual logic to do operations? Well one example I will give here is the adder, we can use logic gates to define a circuit that takes 2 binary registers and calculates their sum into another register, you can look up many explanations for this online but here I will show you my Verilog implementation
Believe it or not, subtraction is just addition in a computer as we can only store numbers of a certain size
Imagine we could only write 3-digit numbers
Lets say we have the number 345
We want to subtract 1, well what happens if we add 999
The result is 1344, but we can only keep the 3 lowest digits
So the result is 344, which is 1 less than 345
If you want to know how this works, look up 2s complement subtraction
These all work in similar ways, there is a logic gate “program” that can perform these operations, in fact logic gates can write any program that a normal programming language could produce, they are “Turing Complete”
The clock matters for determining change in state, calculations always update based on the current state, therefore to allow sequential execution we must
Ensure any register is only updated when the clock is also high (to allow setup of context before a clock pulse)
Ensure calculations don’t feed back into themselves (e.g. alu should have its output in a register not straight out to bus, otherwise having alu out enabled and acc in enabled would cause acc to keep increasing by b until the clock goes low)
These 2 rules allow exactly 1 step to run each clock pulse based on control signals we set (steps can include processes that can run in parallel), this allows us to sequentially execute microcode (operations that build up a single instruction)
If we have a register that stores our current address to execute (called the Program Counter or PC), then the current code to execute is RAM[PC], but this is just a number, how does the computer know what it needs to do?
Well we simply use combinatorial logic, or to explain more simply, we don’t need to think of the current state as context, but simply as an input to a stateless function, if this was the case then we could implement the functionality as an operation, the same as addition or multiplication. if we want a certain number in memory to mean that our acc should be set equal to acc + bregister, then we could consider a function that takes the computers current state, and returns the state of the computer afterwards f(state, PC) -> newState. We know that any operation/function can be implemented with Logic Gates, and therefore, we can implement this function, Let’s say that RAM[PC] = 65, we just need to ensure that f(state,65) returns the correct output state for every input state and we have our function. In short, we can implement Sequential execution as a function from state to state that is triggered every clock pulse.
This was a team project that I completed for my university course for which we received the highest marks in the University.
For this project we created several hacks using DLL Injection
However our primary hack turned this:
Into this:
I operated as Joint Team Leader on this project, and I believe that the culture of our team, focussing on cultivating a fun experience controlled by easily understandable protocol, as well as providing technical help from our different areas of expertise and motivating the fair sharing of ideas, was the primary reason for us reaching the best mark overall.
My housemate and I took the interface to a till screen that we had purchased and wrote a library for display methods, we then built a household clock system that kept the time, temperature, date, etc.
This very website is a side project of mine, unfortunately it has been replaced with a portfolio for now but had contained a pseudo-terminal interface with some hacking challenges including a c++ injection attack and some brute forcing
For one of my university groups, a fun exploration into the discord API.
Scraped YouTube to build network of linked videos, plotted in networkx and in gephi. Found all endings (any infinite loops or terminal nodes). Then created a function to find all routes from the initial video to some specific ending. Used this to find all routes, then followed all of these routes to some degree in order to have seen everything.
I enjoy fiddling with any program’s memory, with newer versions of cheat engine one can Inject C code inline which allows for interesting behaviour, from flying around game maps to having ammo update following the Fibonacci sequence every shot.
Unfortunately, I haven’t monitored everything I have ever done, but from brute forcing my brother’s Christmas quiz website to making my own Library of Babel and giving my friends the index of their darkest secrets, I spend a lot of my time programming